﻿// 线段树和树状数组.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<vector>

using namespace std;

/// <summary>
/// 线段树（区间内做累加查询）
/// </summary>
class SegmentTree
{
    vector<int> tree;   //初始化大小为目标数组元素个数*4-1 线段树长度相关证明详见：https://blog.csdn.net/suncongbo/article/details/77432667
public:
    SegmentTree(int targetArraySize):tree(targetArraySize*4-1) {}
    SegmentTree(vector<int> &arr):tree(arr.size()*4-1)
    {
        buildTree(arr, 0, arr.size() - 1, 0);
    }

    /// <summary>
    /// 采用归并方式建树确保结点储存正确的线段数值
    /// </summary>
    /// <param name="arr">数据源数组</param>
    /// <param name="left">数据源数组的建树左边界</param>
    /// <param name="right">数据源数组的建树右边界</param>
    /// <param name="rootIdx">树根节点在tree数组的索引（调用入口索引为0，树根）</param>
    void buildTree(vector<int>& arr, int left, int right, int rootIdx)
    {
        if (left>=right)
        {
            tree[rootIdx] = arr[left];
            return;
        }
        
        int leftNodeIdx = rootIdx * 2 + 1;
        int rightNodeIdx = rootIdx * 2 + 2;

        int mid = left + ((right - left) >> 1);

        //记忆二分传入规则由于1/2会得0这一特性，当l~r为相邻索引时，为了保证递归调用一定有出口，左右划分为L~mid,mid+1~R较为合适
        buildTree(arr, left, mid, leftNodeIdx);
        buildTree(arr, mid + 1, right, rightNodeIdx);   

        tree[rootIdx] = tree[leftNodeIdx] + tree[rightNodeIdx];
    }

    /// <summary>
    /// 采用归并方式更新路径相关结点
    /// </summary>
    /// <param name="arr">数据源数组</param>
    /// <param name="left">数据源数组的建树左边界</param>
    /// <param name="right">数据源数组的建树右边界</param>
    /// <param name="changeIdx">需要更新的源数组下标</param>
    /// <param name="val">更新的新值</param>
    /// <param name="rootIdx">树根节点在tree数组的索引（调用入口索引为0，树根）</param>
    void updateTree(vector<int>& arr, int left, int right,int changeIdx,int val, int rootIdx)
    {
        if (changeIdx <left || changeIdx>right)     //排除查询区间外的
            return;
        else if (left>=right)
        {
            arr[changeIdx] = val;
            tree[rootIdx] = val;
            return;
        }

        int leftNodeIdx = rootIdx * 2 + 1;
        int rightNodeIdx = rootIdx * 2 + 2;

        int mid = left + ((right - left) >> 1);

        if (changeIdx <= mid)
            updateTree(arr, left, mid, changeIdx, val, leftNodeIdx);
        else
            updateTree(arr, mid + 1, right, changeIdx, val, rightNodeIdx);
        tree[rootIdx] = tree[leftNodeIdx] + tree[rightNodeIdx];
    }

    /// <summary>
    /// 查询区间内的累加
    /// </summary>
    /// <param name="arr"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    /// <param name="queryL">查询左范围边界</param>
    /// <param name="queryR">查询右范围边界</param>
    /// <param name="rootIdx"></param>
    /// <returns></returns>
    int query(vector<int> &arr,int left, int right,int queryL,int queryR,int rootIdx)
    {
        if (queryR<left || queryL>right)    //排除查询区间外的
            return 0;
        else if (left>=right||(queryL<=left&&right<=queryR))    //刚好满足查询边界的直接返回
        {
            return tree[rootIdx];
        }

        int leftNodeIdx = rootIdx * 2 + 1;
        int rightNodeIdx = rootIdx * 2 + 2;

        int mid = left + ((right - left) >> 1);
        int res = 0;
        //归并左右子叶结点的查询值进行累加操作
        res += query(arr, left, mid, queryL, queryR, leftNodeIdx);
        res += query(arr, mid + 1, right, queryL, queryR, rightNodeIdx);
        return res;
    }
};

/*后来证明是错误版本。
*二分法begin、end的mid以是有缺陷考虑不全面的,由于实际递归操作的时源数据数组的可访问索引，
* 因而在建树和搜树时采用带有end这种超出数组索引范围的边界进行递归可能会产生误差
* 知识点：在操作递归边界时若直接使用数据索引建树的操作中不应采用begin和end边界做二分法
* 老老实实用left和right吧
/*
* class SegmentTree
{
	vector<int> tree;
public:
	SegmentTree(vector<int>& arr) :tree(arr.size()*4-1)
	{
		buildTree(arr, 0, arr.size(), 0);
	}

	void buildTree(vector<int>& arr, int begin, int end, int rootNode)
	{
		if (begin+1>=end)
		{
			tree[rootNode] = arr[begin];
			return;
		}

		int leftNode = rootNode * 2 + 1;
		int rightNode = rootNode * 2 + 2;

		int mid = begin + ((end - begin) >> 1);

		buildTree(arr, begin, mid, leftNode);
		buildTree(arr, mid, end, rightNode);
		tree[rootNode] = tree[leftNode] + tree[rightNode];
	}

	int query(vector<int> &arr,int L, int R)
	{
		return query(0, arr.size(), 0, L, R);
	}

	void update(vector<int>& arr, int idx, int val)
	{
		update(arr, 0, arr.size(), 0, idx, val);
	}

private:
	int query(int begin, int end, int rootNode,int L,int R)
	{
		if (R<begin||L>=end)
		{
			return 0;
		}

		if ((begin>=L&&end-1<=R)||begin+1>=end)
		{
			return tree[rootNode];
		}

		int leftNode = rootNode * 2 + 1;
		int rightNode = rootNode * 2 + 2;

		int mid = begin + ((end - begin) >> 1);
		int ans = query(begin, mid, leftNode, L, R);
		ans += query(mid, end, rightNode, L, R);
		return ans;
	}

	void update(vector<int>& arr, int begin, int end, int rootNode,int idx,int val)
	{
		if (idx<begin||idx>=end)
		{
			return;
		}
		if (begin + 1 >= end)
		{
			arr[idx] = val;
			tree[rootNode] = val;
			return;
		}

		int leftNode = rootNode * 2 + 1;
		int rightNode = rootNode * 2 + 2;

		int mid = begin + ((end - begin) >> 1);

		update(arr, begin, mid, leftNode, idx, val);
		update(arr, mid, end, rightNode, idx, val);
		tree[rootNode] = tree[leftNode] + tree[rightNode];
	}
};
*/

/// <summary>
/// 树状数组（作累加操作）
/// https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/solution/shu-zhuang-shu-zu-by-liweiwei1419/
/// </summary>
class BitTree
{
    vector<int> tree;   //与数据源数组一样长
public:
    BitTree(vector<int> &arr)
    {
        buildTree(arr);
    }

    /// <summary>
    /// 获取当前数的lowbit值
    /// 「树状数组」组织成的树是有层级的，下标的二进制表示的最低位 1 后面的 0 的个数决定了，当前结点在第几层；
    /// 这样组织数据，从叶子结点到父结点是可以通过一个叫做 lowbit 的函数计算出来，并且可以知道小于等于当前下标的同一层结点的所有结点。
    /// BitTree索引不可为0，否则将无法取得lowbit值，因而BitTree可用索引为1~N
    /// </summary>
    /// <param name="x"></param>
    /// <returns></returns>
    static int lowbit(int x) { return x & (-x); }  //同可得x&(~x+1) x按位与自己的补码获得lowbit值,lowbit = x & (-x) 仅在x为正数时生效

    /// <summary>
    /// 建树
    /// </summary>
    /// <param name="arr"></param>
    void buildTree(vector<int>& arr)
    {
        tree.resize(arr.size()+1, 0);   //树的可操作索引不能为0，否则将无法取得lowbit值,因而+1跳过索引0对数值进行存储
        for (int i = arr.size()-1; i >=0 ; i--)  
        {
            for (int j = i+1; j < tree.size(); j+=lowbit(j))//tree的操作索引j边界不可为0，所以做了索引+1设计
            {
                tree[j] += arr[i];
            }
        }
    }

    void update(vector<int>& arr, int changeIdx, int val)
    {
        int different = val - arr[changeIdx];
        arr[changeIdx] = val;
        for (int i = changeIdx+1; i < tree.size(); i+=lowbit(i))    //tree的操作索引i边界不可为0，所以做了索引+1设计
        {
            tree[i] += different;
        }
    }

    /// <summary>
    /// 察索引前缀和
    /// </summary>
    /// <param name="idx">数组索引</param>
    /// <returns></returns>
    int query(int idx)
    {
        int sum = 0;

        //利用lowbit特性做遍历累加
        //由于求的是前缀和，于是可以直接利用tree索引+1的特性直使用源数组所需求的前缀的索引直接作为起始边界就能求出对应前缀和
        while (idx>0)
        {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }

    /// <summary>
    /// 利用前缀和察区间
    /// </summary>
    /// <param name="left"></param>
    /// <param name="right"></param>
    /// <returns></returns>
    int query(int left, int right)
    {
        return query(right + 1) - query(left);
    }
};

int main()
{
    //std::cout << "Hello World!\n";
    vector<int> nums = { 1,3,5,7,9 ,11 };
    SegmentTree st(nums);
    st.updateTree(nums, 0, nums.size() - 1, 4, 6, 0);
    int res = st.query(nums, 0, nums.size() - 1, 3, 4, 0);
    //BitTree bt(nums);
    //bt.update(nums, 0, 2);
    //int res=bt.query(2, 3);
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
